package com.zsjt.dynamicprogramming;

import java.util.Scanner;

/**
 * @author ZhanBo
 * @date 2020/8/1
 */
public class CompleteBackpack {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        /*输入背包的最大重量*/
        int maxWeight = scanner.nextInt();
        /*输入物品的数目*/
        int numbers = scanner.nextInt();
        /*物品重量*/
        int [] weight = new int[numbers];
        /*物品价值*/
        int [] value = new int[numbers];

    }

    /**
     * 设f[j]表示重量不超过j公斤的最大价值 可得出状态转移方程 :
     *  f[j]=max{f[j]，f[j−w[i]]+v[i]}
     *  区别：0，1背包是从大到小遍历，完全背包是从小到大遍历
     * @param maxWeight
     * @param weight
     * @param value
     * @return
     */
    public static int method01(int maxWeight, int[] weight, int[] value) {
        /* 第一个值，不算*/
        int n = weight.length - 1;
        int[] f = new int[maxWeight + 1];
        for (int i = 1; i <= n; i++) {
            for (int j = weight[i]; j <= maxWeight; j++) {
                f[j] = Math.max(f[j], f[j - weight[i]] + value[i]);
            }
        }
        /*最优解*/
        return f[maxWeight];
    }
}
